NUMÉRIQUE (ANALYSE)

NUMÉRIQUE (ANALYSE)

Les problèmes et les méthodes numériques ne délimitent pas un secteur spécifique des mathématiques; ils interviennent en effet non seulement dans les domaines traditionnels (analyse classique et équations fonctionnelles), mais aussi en algèbre, en théorie des nombres, etc. La spécificité de l’analyse numérique relève de trois aspects majeurs:

– une démarche originale combinant les possibilités théoriques et expérimentales, où le développement des moyens de calcul sur ordinateurs joue un rôle déterminant;

– le développement de concepts et de méthodes de type quantitatif en mathématiques, en liaison étroite avec d’autres disciplines, notamment les sciences physiques et l’informatique;

– l’élaboration de méthodes directement liées aux problèmes posés.

Dans cette encyclopédie, le parti a été pris de développer les aspects numériques dans chacun des différents articles. Nous nous bornerons ici à classer les problèmes et à renvoyer aux articles correspondants.

Pour les équations numériques à une variable, on se reportera à histoire du CALCUL NUMÉRIQUE; pour les problèmes linéaires et les problèmes d’optimisation, aux articles traitement numérique des MATRICES et PROGRAMMATI; pour les problèmes non linéaires à plusieurs variables, notamment la méthode de descente et la méthode du gradient, voir également PROGRAMMATION. Enfin, pour les équations différentielles, on se reportera au chapitre 7 de l’article équations DIFFÉRENTIELLES et, pour les équations aux dérivées partielles, à l’article équations aux DÉRIVÉES PARTIELLES - Analyse numérique.

1. Problèmes et méthodes numériques

Le rôle de l’analyse numérique

L’analyse numérique tient une place capitale dans les interventions des mathématiques, aussi bien en sciences physiques que dans le domaine de la biologie, des technologies et des sciences économiques et sociales. Mais elle offre aussi des possibilités très riches pour les sciences mathématiques elles-mêmes: sans oublier que, dans le passé, les problèmes numériques ont constitué un moteur pour le développement des concepts de l’analyse (cf. histoire du CALCUL NUMÉRIQUE), il convient de souligner que le développement récent des moyens de calcul scientifique a ouvert de nouvelles perspectives:

– le traitement de problèmes classiques à un niveau beaucoup plus complexe (par exemple la résolution de systèmes linéaires à un grand nombre d’inconnues et d’équations différentielles);

– le traitement de problèmes que les moyens classiques ne permettaient même pas d’aborder (équations aux dérivées partielles, problèmes variationnels, codages...);

– la simulation de problèmes (comportement des systèmes dynamiques discrets et continus, problèmes aux limites) permettant d’étudier l’influence des paramètres, la stabilité des solutions et les singularités;

– des calculs portant non seulement sur des nombres ou des systèmes de nombres, mais sur des objets formels (polynômes, fonctions transcendantes élémentaires, fonctions spéciales);

– l’expérimentation: découverte et invalidation de conjectures, notamment en théorie des nombres;

– la démonstration «automatique» de théorèmes: la résolution du problème des quatre couleurs, ou l’étude de la structure des groupes finis simples (cf. GROUPES - Groupes finis, chap. 2) en sont des exemples frappants.

Ces possibilités ont un effet en retour: la construction d’algorithmes et l’étude comparée de leur performance interviennent maintenant dans l’ensemble des mathématiques.

Dans la suite de ce texte, on traitera essentiellement des concepts et des méthodes de l’analyse numérique proprement dite, en renvoyant à l’article ALGORITHMIQUE pour des aspects complémentaires.

Concepts et méthodes de l’analyse numérique

Le concept d’approximation

Dans toutes les questions de représentation des nombres et des fonctions (cf. représentation et approximation des FONCTIONS), il faut distinguer la recherche de solutions «exactes» de celle d’algorithmes d’«approximation» d’une solution. Mais on notera que le champ du concept d’approximation recouvre non seulement les problèmes issus de l’analyse mais aussi certaines questions purement algébriques. Ainsi, en algèbre linéaire, les méthodes itératives sont employées pour la résolution des systèmes (méthode de relaxations successives, de Gauss-Seidel, de Jacobi), pour la recherche des valeurs propres dominantes (quotient de Rayleigh) et pour la diagonalisation des matrices (cf. traitement numérique des MATRICES).

Le discret et le continu . Fondamentalement, l’analyse numérique établit un rapport organique entre le continu et le discret. Le plus souvent, on approche un problème continu par un problème discret portant sur une suite finie de nombres: parmi les nombreux exemples, citons les valeurs d’une fonction, les calculs d’intégrales, la résolution d’équations différentielles ou aux dérivées partielles. Mais il existe aussi des cas où il est commode d’approcher un problème discret peu accessible au calcul par un problème continu: comparaison de séries à des intégrales (cf. calculs ASYMPTOTIQUES), utilisation de lois continues en probabilité et en statistique.

L’aspect algorithmique. C’est une des originalités essentielles du point de vue numérique en analyse. On ne s’intéresse pas seulement à l’existence de suites d’approximation d’un nombre ou d’une fonction mais à la recherche d’algorithmes, c’est-à-dire de procédures explicites de calcul des termes successifs d’une telle suite, et à l’étude de leur pertinence, ce qui conduit à la mise en place de plusieurs concepts quantitatifs que nous décrivons rapidement.

Précision et erreurs. Pour évaluer la précision d’un résultat, on doit prendre en compte trois types d’erreurs:

– les erreurs de méthode , relatives à la précision de l’algorithme utilisé;

– les erreurs d’arrondi , liées à l’exécution des calculs;

– les erreurs sur les données elles-mêmes.

Prenons un exemple très simple, à savoir l’approximation d’une valeur de sin x à l’aide du développement en série:

1. On remplace la série par une somme partielle; l’erreur de méthode s’obtient en majorant le reste Rⁿ .

2. Dans le calcul de Sⁿ , la calculatrice arrondit les nombres à une précision donnée, par exemple 10^-8.

3. Si x est un nombre irrationnel, la donnée elle-même est une valeur approchée.

Dans certains cas, il y a même des erreurs dues à la modélisation du phénomène étudié (linéarisation d’équations aux dérivées partielles par exemple).

Stabilité, perturbations . Le concept de stabilité est d’importance primordiale. Il concerne non seulement l’approximation des fonctions ou des formes linéaires sur des espaces fonctionnels, mais aussi les équations numériques ou fonctionnelles elles-mêmes. Il s’agit alors d’étudier la dépendance des solutions d’une telle équation par rapport aux paramètres (second membre, coefficients, etc.). Ici les résultats qualitatifs (continuité, différentiabilité) ne suffisent pas et on a besoin de majorations explicites, par exemple de type lipschitzien. Si la condition de stabilité est satisfaite, on dit parfois que le problème est bien posé .

Ce concept de stabilité intervient aussi dans l’étude des perturbations . Soit à étudier le comportement des solutions d’un problème P où intervient un paramètre «petit». Pour cela, on néglige dans un premier temps l’effet de en étudiant le problème P⁰, en général beaucoup plus simple, puis on cherche à approcher les solutions de P par un développement asymptotique autour de = 0. Bien entendu, cette méthode n’est valable que si le problème est stable; on dit alors que la perturbation est régulière , et on dit qu’elle est singulière dans le cas contraire.

Par exemple, pour l’équation:

la perturbation est régulière: sachant que 1 est une racine de l’équation non perturbée x ³ 漣 x = 0, on peut approcher une solution a size=1^凞 de (1) sous la forme a size=1^凞 = 1 + 見凞 + 廓凞² + ... en déterminant de proche en proche les coefficients 見, 廓, ... par identification, et il en serait de même pour les autres racines.

En revanche, pour l’équation:

la perturbation est singulière car le module d’une des deux racines tend vers l’infini lorsque tend ves 0; cette racine ne peut donc pas être obtenue à partir de l’équation x 漣 1 = 0.

Les méthodes de perturbation sont d’usage fréquent dans l’étude des équations différentielles (cf. équations DIFFÉRENTIELLES, chap. 6, PERTURBATIONS, SYSTÈMES DYNAMIQUES) et des équations aux dérivées partielles (méthode WKB en mécanique quantique par exemple).

Rapidité de convergence, performance . Pour apprécier la pertinence d’un algorithme d’approximation, on dégage plusieurs aspects:

– Un aspect mathématique qualitatif (existence de solutions, unicité, stabilité topologique, etc.).

– Un aspect mathématique quantitatif (rapidité de convergence du processus d’approximation utilisé, optimisation).

– Un aspect quantitatif relevant à la fois des mathématiques et de l’informatique, à savoir la performance , où l’on prend en compte le temps total d’exécution du calcul pour obtenir une précision donnée. La rapidité de convergence n’est pas le seul facteur en jeu; interviennent aussi la complexité des calculs à chaque pas, les méthodes de programmation et le type de matériel informatique utilisé. Les outils théoriques concernent la complexité des expressions ^{[cf. RÉCURSIVITÉ]} et la complexité des algoritimes ^{[cf. ALGORITHMIQUE]}.

Lorsque la performance d’un algorithme est insuffisante, on peut soit changer d’algorithme, soit procéder à des accélérations de convergence (cf. infra : Accélérations de convergence ).

Les méthodes d’approximation

Les principales méthodes d’approximation relèvent de deux idées dominantes.

1. Discrétisation par interpolation (en remplaçant par exemple un opérateur différentiel par un opérateur aux différences finies; la méthode des éléments finis est aussi de ce type).

2. Représentation des solutions par des intégrales (transformées de Fourier, de Laplace, etc.) ou des séries (séries entières, séries de Fourier ou séries de polynômes orthogonaux), suivie d’une approximation portant sur ces représentations.

Les méthodes de discrétisation ont un champ d’application plus large, mais les méthodes de représentation fournissent une information qualitative plus riche.

En outre, très souvent, on ne s’intéresse pas à la solution elle-même de l’équation fonctionnelle, mais aux valeurs d’une forme linéaire sur cette solution (par exemple l’intégrale). D’où l’importance non seulement des techniques d’approximation des fonctions, esquissées dans représentation et approximation des FONCTIONS, mais de l’étude de l’approximation des valeurs d’une forme linéaire (cf. infra : Approximation des valeurs d’une forme linéaire ).

Méthodes internes, externes . Pour approcher une solution f d’une équation fonctionnelle appartenant à un espace donné H de fonctions, il est naturel de choisir les éléments f ⁿ de la suite d’approximation dans H; on dit alors que la méthode est interne . Mais, dans certains cas, on peut être amené à choisir les f ⁿ en dehors de H, auquel cas la méthode est dite externe .

Ainsi, lorsque f est solution d’un problème de Cauchy pour une équation différentielle, la méthode des approximations successives ou le développement en série entière sont des méthodes internes, tandis que la méthode du pas-à-pas d’Euler ou la méthode de Runge-Kuta, qui mettent en jeu des fonctions polynomiales par morceaux, sont externes (cf. équations DIFFÉRENTIELLES, chap. 7). Il en est de même pour les équations aux dérivées partielles, dans l’étude des problèmes aux limites. Le cas standard est le suivant: on considère un opérateur différentiel auto-adjoint A à résolvante compacte dans un espace hilbertien H. Pour résoudre l’équation A(u ) = f , on introduit la base hilbertienne ( 﨏ⁿ ) des fonctions propres de A (cf. équations INTÉGRALES, théorie SPECTRALE) et on approche u par sa projection orthogonale u ^p sur le sous-espace vectoriel engendré par 﨏¹, ..., 﨏^p ; cette méthode, due à Galerkine, ne s’applique que si l’on connaît les fonctions propres. Les méthodes d’éléments finis sont aussi des méthodes internes. En revanche, pour les équations de la mécanique des fluides incompressibles, on fait appel à des méthodes externes.

2. Approximation des valeurs d’une forme linéaire

Le problème de l’approximation des valeurs d’une forme linéaire est étroitement lié à celui de l’approximation des fonctions. On se référera fréquemment aux chapitres 5, 7 et 8 de l’article représentation et approximation des FONCTIONS.

Problématique

On se donne une forme linéaire continue L sur un espace vectoriel normé de fonctions E.

Voici deux exemples fondamentaux:

– Intégrale . E = 暈([a , b ]) est ici l’espace des fonctions continues sur [a , b ] muni de la norme N size=1^秊 et:

plus généralement, si 神 est un poids , c’est-à-dire une fonction continue strictement positive sur ]a , b [ telle que:

on prend:

– Dérivée en un point . Ici E = 暈¹([a , b ]), muni de la norme f 料 N size=1^秊(f ) + N size=1^秊(f ) et:

Un cadre unificateur pour ces deux types d’exemples est celui des mesures et des distributions.

La difficulté de calculer des valeurs approchées de L(f ) provient du fait que, dans la plupart des cas, on connaît les valeurs de f , voire des valeurs approchées, en certains points seulement de [a , b ]. On est donc amené à approcher L par une mesure 猪 à support fini, c’est-à-dire à approcher L(f ) par:

Plus généralement, on veut étudier les processus linéaires d’interpolation de L par des formes linéaires continues Lⁿ sur E. Il convient de noter qu’il s’agit ici de convergence faible , c’est-à-dire que, pour tout f de E, la suite (Lⁿ (f )) tend vers L(f ). Très souvent, pour approcher L(f ), on se donne un processus linéaire d’approximation de f , c’est-à-dire une suite (u ⁿ ) d’endomorphismes continus de E tels que u ⁿ (f ) converge vers f (cf. représentation et approximation des FONCTIONS, chap. 7) et u ⁿ (g ) converge vers g pour g appartenant à un sous-espace dense de E, par exemple si g est un polynôme. On approche alors L(f ) par Lⁿ (f ) = L(u ⁿ (f )). De ce point de vue, l’étude du processus (Lⁿ ) se ramène à celle des processus (u ⁿ ). Mais il y a une différence essentielle: dans le cas du processus (u ⁿ ), on s’intéresse à la convergence au sens de la norme de E, tandis que, pour le processus (Lⁿ ), on s’intéresse à la convergence de L(u ⁿ (f )) vers L(f ) dans C. Il en est de même pour l’étude de la stabilité, de la convergence et de l’optimisation.

Les résultats concernant la stabilité et la consistance s’expriment ici de la manière suivante.

Théorème 1. On suppose E complet. Si le processus d’approximation est stable, c’est-à-dire si la suite de terme général 瑩Lⁿ 瑩 est bornée, et si Lⁿ (g ) tend vers L(g ) pour g appartenant à un sous-espace dense de E, alors Lⁿ (f ) tend vers L(f ) pour tout f de E.

Soit, en particulier, E = 暈([a , b ]) muni de la norme N size=1^秊. Si 瑩Lⁿ 瑩 諒 M et si, pour tout monôme x ^p , Lⁿ (x ^p )L(x ^p ), alors, pour toute fonction continue f , Lⁿ (f )L(f ).

Le cas des formes linéaires positives est particulièrement simple, en raison du résultat suivant qui exprime qu’une forme linéaire positive sur 暈([a , b ]) est une mesure de Radon.Théorème 2. Toute forme linéaire positive 﨏 sur l’espace vectoriel 暈([a , b ]) muni de la norme N size=1^秊 est continue.

Plus précisément:

par suite 瑩 﨏 瑩 = | 﨏(1)|.

Dans le cas des mesures à support fini, où 猪 est donné par la formule (1), alors 瑩 猪 瑩 = |^j |. Si 猪 est positive, on a 瑩 猪 瑩 = ^j = 猪(1); en revanche, si les^j ne sont pas tous positifs, il peut arriver que, par compensation de signes, | 猪(1)| soit petit, bien que 瑩 猪 瑩 soit très grand.

En combinant les théorèmes 1 et 2, on obtient ce qui suit.

Théorème 3. Soit L et (Lⁿ ) des formes linéaires positives sur 暈([a , b ]). Si, pour tout monôme x ^p , Lⁿ (x ^p )L(x ^p ), alors:

(a ) le processus (Lⁿ ) est stable, car 瑩Lⁿ 瑩 = |Lⁿ (1)|L(1);

(b ) le processus est convergent, c’est-à-dire, pour toute fonction continue f , Lⁿ (f )L(f ).

Plaçons-nous maintenant dans le cas particulièrement important où (Lⁿ ) est défini d’une suite (p ⁿ ) de projecteurs de 暈([a , b ]) sur le sous-espace vectoriel 戮ⁿ des polynômes de degré 諒 n , c’est-à-dire où Lⁿ (f ) = L(p ⁿ (f )); les interpolations de Lagrange ou d’Hermite constituent des exemples significatifs de cette situation.

Dans ces conditions, on a l’estimation suivante de la précision :

où 嗀ⁿ (f ) désigne la distance de f au sous-espace 戮ⁿ (cf. représentation et approximation des FONCTIONS, chap. 7; l’étude de 嗀ⁿ (f ), qui met en jeu la régularité de la fonction f , est faite au chapitre 8 de représentation et approximation des FONCTIONS).

Pour étudier la convergence et la rapidité de la convergence du processus (Lⁿ ), il suffit d’évaluer les nombres 瑩Lⁿ 瑩, appelés constantes de Lebesgue du processus.

Théorème 4. Cas des formes linéaires positives.

Lorsque L et Lⁿ sont des formes linéaires positives, alors, pour toute fonction continue f ,

Ainsi, la rapidité de convergence ne dépend que de la régularité de f .

Nous verrons dans la suite comment ces différents résultats interviennent dans le calcul approché des intégrales.

Calcul approché des intégrales

Cadre théorique

Soit f une fonction continue sur [ 見, 廓]. Pour obtenir des valeurs approchées de:

on effectue une subdivision à pas constants de [ 見, 廓] et, sur chaque intervalle [a , b ] ainsi déterminé, on effectue une interpolation de f par une fonction polynomiale de degré 諒 p où p est un entier donné.

On introduit donc un système interpolateur S = 見⁰, 見¹, ..., 見^p de points de [a , b ] et le noyau interpolateur:

mais, cette fois, on ne s’intéresse pas au polynôme L^S(f ) d’interpolation de Lagrange associé à f (cf. représentation et approximation des FONCTIONS, chap. 5) mais à son intégrale sur [a , b ]. On est alors amené à étudier le problème suivant: Soit P un élément de l’espace vectoriel 戮^p des polynômes de degré 諒 p ; peut-on exprimer:

comme combinaison linéaire des valeurs P( 見^j )? Plus précisément, on a le théorème suivant.

Théorème 1. Interpolation de l’intégrale d’un polynôme.

Il existe une suite⁰, ...,^p et une seule de nombres complexes telle que, pour tout polynôme P 捻 戮^p , on ait:

En effet, les formes linéaires 嗀^j : P 料P( 見^j ) sont indépendantes, donc forment une base de l’espace vectoriel des formes linéaires sur 戮^p . L’intégrale se décompose donc de manière unique dans cette base.

Pour le calcul explicite des coefficients^j , on prend des polynômes convenablement choisis, par exemple:

Si maintenant f est une fonction non polynomiale, on approche:

par:

Le problème est alors de majorer |I(f ) 漣 I^S(f )|. On remarque pour cela que I(f ) = I^S(f ) pour f 捻 戮^p . Ainsi, lorsque f est suffisamment régulière, l’erreur commise en remplaçant I(f ) par I^S(f ) provient des termes d’ordre 礪 p dans le développement de Taylor, en a par exemple. Plus précisément, comme I^S(f ) = I(L^S(f )) et comme la fonction f 漣 L^S(f ) s’annule aux points 見^j , le théorème de division des fonctions différentiables (cf. représentation et approximation des FONCTIONS, chap. 2) permet de prouver le résultat qui suit.

Théorème 2. Estimation de la précision.

Soit f une fonction de classe C^{p +1} sur [a , b ] à valeurs complexes; alors:

où:

On obtient une autre estimation, beaucoup plus fine que celle qui est donnée par le théorème 2, par la théorie de l’optimisation. En appliquant le théorème 4 du chapitre précédent, on obtiendra ce qui suit.

Théorème 3. Estimation optimale de la précision.

Soit f une fonction continue sur [a , b ]; alors:

où 嗀^p (f ) est la distance de f au sous-espace vectoriel 戮^p des polynômes de degré 諒 p et où K^S est la constante de Lebesgue du système interpolateur S, à savoir:

En particulier, si tous les nombres^j sont positifs, alors, en prenant P = 1 dans la relation (1), on a:

si bien que:

On voit donc apparaître l’avantage des processus à coefficients positifs.

Dans la suite de ce chapitre, nous étudierons successivement les méthodes élémentaires, la méthode de Newton-Cotes, puis les méthodes optimales gaussiennes.

Méthodes élémentaires

Pour approcher:

on effectue par dichotomie une subdivision de [ 見, 廓] à pas constant:

(ce qui est bien adapté au calcul numérique sur ordinateur) et, sur chaque intervalle partiel [a , b ], on effectue une interpolation de f par un polynôme de petit degré p .

a ) Méthode des rectangles (p = 0).

Ici, N = (X 漣 a ); on approche f sur [a , b ] par la constante f (a ), d’où:

On approche donc:

par:

la précision est contrôlée par:

La rapidité de convergence est désastreuse.

b ) Méthode des trapèzes (p = 1).

Ici N = (X 漣 a )(X 漣 b ); on effectue une interpolation linéaire de f sur [a , b ]; alors:

On approche donc:

par:

La précision est contrôlée par:

c ) Méthode de la tangente ou du milieu (p = 1).

Ici N = (X 漣 a + b 2)²; on effectue une interpolation de f par la tangente au point d’abscisse (a + b )/2; alors:

On approche donc:

par:

la précision est contrôlée par:

d ) Méthode de Simpson (p = 2).

Ici N = (X 漣 a )(X 漣 b )(X 漣 a + b 2); on effectue une interpolation parabolique de f ; alors:

formule dite des trois niveaux .

Ici, il se trouve que la formule interpolatoire (1) est vraie, non seulement si d ⁰P 諒 2, mais encore si d ⁰P 諒 3; on peut donc remplacer le polynôme interpolateur de Lagrange L^S(f ) par le polynôme interpolateur de Hermite H^S(f ) relatif au noyau N = (X 漣 a )(X 漣 b )(X 漣 a + b 2)² sans changer la valeur de I^S(f ). En appliquant la majoration (3) à ce dernier cas, on obtient:

En définitive, on approche l’intégrale:

par:

La précision est contrôlée par:

Cette fois, la rapidité de convergence est en 1/32ⁿ , et la performance est acceptable, puisque le calcul de I^{R(n )} et I^{M(n )} équivaut sensiblement à celui de I^{R(2n )}.

Méthode de Newton-Cotes

La méthode de Newton-Cotes consiste à ne pas subdiviser l’intervalle [ 見, 廓] et approcher la fonction f sur [ 見, 廓] = [a , b ] par un polynôme d’interpolation L^S(f ) de degré p , où S est la subdivision de pas constant h = (b 漣 a )/p .

Dans cette méthode, le cas où p est impair est plus favorable que le cas pair. En outre, à partir de p = 9, la forme linéaire

n’est plus positive car, dans la formule (1), certains des coefficients^j sont négatifs. On peut même prouver que 瑩L^p 瑩+ 秊 avec une croissance géométrique. Ce procédé est donc instable; il peut diverger, même si f est analytique. C’est pourquoi, dans les méthodes à pas constant, il convient de subdiviser [ 見, 廓] en n intervalles et, sur chacun des intervalles obtenus, de prendre la méthode de Simpson (p = 3).

Nous verrons au chapitre 3 que l’on peut ensuite améliorer considérablement la performance par accélération de convergence. Néanmoins, ces méthodes ne conviennent que si la longueur de l’intervalle d’intégration reste raisonnable.

Méthodes optimales

C’est à propos de sa célèbre conjecture sur les nombres premiers, comparant 神(n )/n au logarithme intégral:

(cf. théorie des NOMBRES - Théorie analytique des nombres, chap. 2), que Gauss a été amené à approcher des intégrales de t 料 1/Log t sur des intervalles de longueur 10⁵. Les méthodes classiques étant inopérantes, Gauss a étudié la manière de choisir les points de subdivision pour que la précision soit optimale.

À cet effet, on part du fait que si la formule interpolatoire (1) est vraie pour tout polynôme P de degré 諒 r , où r 諒 p , alors l’erreur commise pour une fonction f , non nécessairement polynomiale, est d’autant plus petite que r est grand (cf. (3)). On est donc amené à poser le problème suivant: comment choisir les points 見^j de subdivision pour que (1), déjà vraie si d ⁰P 諒 p , reste vraie si d ⁰P 諒 r , le nombre r étant le plus grand possible. Or la relation (1) n’est pas vérifiée si P = ², carré du polynôme interpolateur, et donc r 諒 2p + 1. Inversement, si r = 2p + 1, la réponse est positive.

Théorème 1. Interpolation de Gauss.

1. Il est équivalent de dire:

a ) la relation (1) est vérifiée pour tout polynôme de degré 2 p + 1;

b ) pour tout polynôme Q de degré 諒 p , on a la relation d’orthogonalité:

Ainsi, lorsque [a , b ] = [ 漣 1, 1], N est proportionnel au polynôme de Legendre L^{p +1} de degré p + 1 (cf. polynômes ORTHOGONAUX), c’est-à-dire que les points interpolatoires 見^j sont les racines de ce polynôme; en particulier, ¹ = X, ² = X² 漣 1/3, ³ = X³ 漣 3 X/5.

2. Sous les conditions précédentes,

En particulier, les coefficients^j sont positifs.

Le noyau étant ainsi choisi, on approche:

par:

La qualité de cet algorithme est précisée par les deux résultats suivants.

Théorème 2. Stabilité de la méthode de Gauss.

Pour tout p , la forme linéaire I^{G(p )} est positive; par suite 瑩I^{G(p )} 瑩 = b 漣 a . Ainsi, le processus de Gauss est stable et consistant. En particulier, pour toute fonction continue f ,

ce qui garantit la convergence pour toute fonction continue f , cette convergence étant d’autant plus rapide que f est régulière.

Théorème 3. Précision de la méthode de Gauss.

Pour tout entier p ,

Pour les fonctions usuelles, le second membre converge rapidement vers 0, même si la longueur de [a , b ] est grande.

Même si p est petit, la précision est bien meilleure que pour les méthodes à pas constant. Ainsi, dans le cas de l’interpolation linéaire (p = 1),

et:

ce qui est déjà plus performant que la méthode de Simpson.

Jacobi a étendu la méthode de Gauss au cas des intégrales avec poids de la forme:

où f est continue bornée sur I. La répartition optimale est alors obtenue en prenant pour noyau interpolatoire un polynôme proportionnel au polynôme orthogonal de degré p + 1 associé au poids 神. Tous ces processus conduisent encore à des formes linéaires positives; la stabilité et la convergence sont donc assurées.

Extensions diverses

– Dans le cas d’intégrales sur un intervalle non compact, par exemple:

on peut utiliser des estimations asymptomatiques du reste:

pour se ramener à:

(cf. calculs ASYMPTOTIQUES).

– La méthode d’approximation par les fonctions splines cubiques (cf. représentation et approximation des FONCTIONS, chap. 5) fournit un algorithme de bonne précision, mais peu performant vu la complexité des calculs.

– Enfin, le calcul de coefficients de Fourier d’une fonction périodique, ou de transformées de Fourier, se rencontre très fréquemment. On peut alors améliorer sensiblement la performance en se servant de la périodicité des fonctions exponentielles circulaires; l’algorithme correspondant, très utilisé, est connu sous le nom de transformation de Fourier rapide.

3. Accélérations de convergence

Problématique

On suppose donnée une forme linéaire continue L sur un espace vectoriel normé de fonctions E et un processus linéaire d’interpolation (Lⁿ ) de L. Pour tout élément f de E, la suite numérique a ⁿ = Lⁿ (f ) converge ou non vers a = L(f ); il peut arriver que la suite (a ⁿ ) diverge, ou encore qu’elle converge vers a , mais trop lentement pour être utilisable en analyse numérique.

Voici deux exemples très élémentaires mais fondamentaux d’une telle situation.

Sommes de séries. Ici E est l’espace vectoriel l¹(C) des suites sommables muni de la norme ¹. L’application qui à u = (u ^p ) associe

est une forme linéaire continue qu’on approche par les sommes partielles Sⁿ (u ) = s ⁿ ; ici le processus d’approximation est stable, puisque 瑩Sⁿ 瑩 = 1. La qualité de l’approximation de S(u ) est mesurée par le reste r ⁿ = (S 漣 Sⁿ )(u ).

L’exemple classique des séries de Riemann

montre que la convergence peut être lente puisque alors:

lorsque 見 = 2, il faudrait prendre 10¹⁰ termes pour obtenir la précision 10^-10.

Dans d’autres cas, les sommes partielles divergent vers + 秊 mais, par un développement asymptotique, on se ramène à l’étude d’une suite convergente. L’exemple de la série harmonique:

est frappant:

on cherche alors à approcher la constante d’Euler:

Intégrales. Ici E = 暈([a , b ]) est l’espace vectoriel des fonctions continues sur [a , b ] à valeurs complexes muni de la norme N size=1^秊. L’application qui à un élément f associe:

est une forme linéaire continue qu’on peut approcher par un processus interpolatoire (Iⁿ ). Dans la méthode des rectangles, ou des trapèzes, on a 瑩Iⁿ 瑩 = 1, et le processus est donc stable, mais la rapidité de convergence est médiocre, de l’ordre de 1/n pour les rectangles et de 1/n ² pour les trapèzes.

Pour améliorer la performance, on peut soit changer complètement d’algorithme d’approximation – pour les intégrales, on peut, par exemple, recourir à des méthodes gaussiennes –, soit garder le même algorithme de base (Lⁿ ) mais améliorer sa rapidité de convergence par des transformations purement algébriques portant sur la suite (Lⁿ (f )); on dit alors qu’on effectue une accélération de convergence. Dans la suite, nous décrirons deux exemples significatifs de telles méthodes d’accélération: la première, de portée très générale, s’appelle méthode d’extrapolation à la limite; elle utilise des barycentrations. La seconde, due à Euler, s’applique aux séries alternées et, plus généralement, aux séries trigonométriques.

Méthode d’extrapolation à la limite

La méthode d’extrapolation à la limite consiste à utiliser une évaluation asymptotique de la différence Lⁿ (f ) 漣 L(f ). Pour des commodités d’écriture, on utilisera pour les suites la notation fonctionnelle a (n ) = Lⁿ (f ) et a = L(f ).

Principe

Plaçons-nous d’abord dans l’hypothèse simple où l’on a établi que:

avec |k | 麗 |k | 麗 1 et 捻 C.

Trois cas peuvent se présenter:

I. On connaît explicitement k et. Pour accélérer la convergence, il suffit évidemment de corriger la suite (a (n )) en posant:

II. On connaît explicitement le nombre k mais pas le coefficient. On effectue alors une barycentration de a (n ) et a (n + 1) de manière à éliminer le terme inconnuk ⁿ ; on écrit:

d’où:

ce qui conduit à poser:

dans ces conditions, on a

III. On connaît seulement l’existence de k et sans connaître leur valeur explicite. On se ramène alors au cas (II) en remplaçant k par une valeur approchée; on observe que:

On pose alors:

dans ces conditions,

Cette méthode s’applique aussi au cas où l’on a établi que:

où O 麗 見 麗 見 , en introduisant la suite a (2^p ).

Exemples

Cas I. Considérons la série:

Ici, on sait que:

on accélère donc la convergence en posant:

Cas II. Soit l’approximation de 神 par la méthode des polygones réguliers ^{[cf. ALGORITHMIQUE]}. Ici:

où = 漣 神³/6 est évidemment inconnu.

On prend:

et:

cette accélération de la méthode d’Archimède est due à Huygens.

Cas III. On s’intéresse à l’approximation d’une solution a de l’équation numérique f (x ) = x , lorsque 0 麗 |f (a )| 麗 1, par la suite définie par la relation a (n + 1) = f (a (n )). Cette fois:

cette fois a et f (a ) sont inconnus. Cette accélération de convergence est connue sous le nom de méthode d’Aitken.

Généralisations

On suppose que a (n ) 漣 a admet un développement asymptotique de la forme:

on notera que le cas où r ⁿ admet un développement asymptotique de la forme:

se ramène au précédent en introduisant la suite (a (n )) de terme général a (n ) = a (2ⁿ ).

Reprenons les trois cas rencontrés ci-dessus.

Cas I. On connaît explicitement le développement asymptotique. Il suffit alors de corriger la suite (a (n )) à l’aide de ce développement en posant:

Ce cas se présente notamment pour les sommes de séries:

et les intégrales:

lorsque f est une fonction de classe C size=1^秊; en effet, la formule d’Euler-Mac Laurin (cf. calculs ASYMPTOTIQUES) fournit un développement asymptotique explicite de a (n ) 漣 a , d’utilisation commode si l’expression de f et de ses dérivées successives est simple.

Les séries de Riemann, la constante d’Euler et le développement de Stirling de n ! fournissent des exemples frappants.

Cas II. On sait que le développement asymptotique (1 ) existe, les nombres k ^j sont connus mais on ne connaît pas les coefficients^j .

On itère la barycentration (3). Plus précisément, on introduit dans l’espace vectoriel l size=1^秊, muni de la norme N size=1^秊, des suites bornées, l’endomorphisme R^k , avec 0 麗 k 麗 1, défini par:

il est immédiat que R^k est continu et que:

Sous l’hypothèse (1 ) on a alors:

En outre, cette méthode conduit à un processus stable . En effet:

or dans les cas usuels k ^j = k ^j . Par suite, la série géométrique:

converge et il en est de même du produit infini de terme général (1 + k ^j )/(1 漣 k ^j ).

Cette méthode d’accélération de convergence, très performante, s’applique notamment au calcul de sommes de séries:

et d’intégrales:

lorsque f est indéfiniment dérivable, dans le cas où le calcul des dérivées successives de f est trop compliqué pour appliquer directement la formule d’Euler-Mac Laurin. Elle s’applique aussi à l’approximation des solutions des équations différentielles par la méthode du pas-à-pas d’Euler (cf. équations DIFFÉRENTIELLES, chap. 7), ou par des méthodes plus performantes.

Déjà utilisée par Euler et les mathématiciens du XVIII^e siècle sur des exemples, la méthode précédente a été popularisée par Romberg à propos du calcul approché des intégrales. Son cadre théorique général a été dégagé par Richardson en 1927.

Pour illustrer la performance de cette méthode, reprenons l’exemple très simple du calcul de 神 par la méthode des polygones réguliers évoquée plus haut. Ici:

on peut donc appliquer la méthode de Richardson en posant:

On trouve que:

Rappelons, pour illustrer cet exemple, que 神 年 3,141 592 653 6, à la précision 10^-10.

Le cas du calcul approché d’une intégrale:

où f est de classe C size=1^秊 est particulièrement intéressant. Cette fois, on part soit de la méthode des rectangles, soit de la méthode des trapèzes. Par la formule d’Euler-Mac Laurin, on a:

où:

Par ailleurs:

(cf. supra : Approximation des valeurs d’une forme linéaire ). L’effet du premier pas d’accélération de convergence est de transformer respectivement la méthode des rectangles en la méthode du milieu et la méthode des trapèzes en la méthode de Simpson. Les pas suivants fournissent des méthodes nettement plus performantes.

La méthode d’accélération de convergence de la suite I^{T(n )}(f ) est d’emploi très fréquent sur les ordinateurs.

En pratique, on calcule les suites I^{R(n )}(f ) par itération, en observant que, dans le passage de n à n + 1, les points de la subdivision précédente sont conservés (d’où le choix de la dichotomie). Ainsi, l’obtention de ces sommes jusqu’à l’ordre n ne nécessite que le calcul de 2ⁿ valeurs de f .

Les sommes a ⁰(n ) = I^{T(n )} s’en déduisent aussitôt par la relation (10); on applique alors à ces sommes les opérateurs R⁴, R⁸, R¹⁶, ..., R^22p , etc., et on obtient ainsi a ¹(n ), ..., a ^p (n ).

Enfin:

qui résulte aussitôt de (9) et (10). Pour obtenir la précision 10^-r , il suffit donc d’arrêter l’algorithme dès que :

ce qui est le test d’arrêt de Runge.

Cas III. On sait que le développement asymptotique existe, mais on ne connaît ni les nombres k ^j ni les coefficients^j . On peut alors itérer le procédé d’Aitken décrit par les formules (5) et (6), mais cette fois les conditions de stabilité sont moins bonnes.

Cette méthode peut s’appliquer à la recherche de solutions approchées d’équations numériques par la méthode des approximations successives.

Méthode d’Euler pour les séries alternées

La méthode d’Euler pour les séries alternées est fondée sur le calcul aux différences finies.

On se propose de chercher des valeurs approchées de la somme d’une série alternée du type:

où f est une fonction positive de classe C size=1^秊 sur [0, + 秊[, telle que, pour tout entier naturel p , (face=F0019 漣 1)^p f ^{(p )} 閭 0.

Le cas de référence est f (x ) = 1/x size=1^見, 見 礪 0; la rapidité de convergence est alors médiocre, puisque le reste est de l’ordre du premier terme négligé, c’est-à-dire 1/n size=1^見.

Euler écrit la somme s sous la forme:

Le caractère alterné est conservé, mais on a remplacé f (n ) par f (n ) 漣 f (n + 1) qui est d’ordre 1/n size=1^見+1. On itère alors ce processus; en outre, on applique cette transformation non pas à la somme s mais à un reste r ⁿ de cette série:

Pour donner une description plus précise de cette méthode, on introduit l’endormorphisme aux différences finies de C size=1^秊(R⁺) défini par:

À l’issue de la première étape:

à la n -ième étape:

où:

Les hypothèses assurent la convergence de toutes les séries et la majoration:

Cette méthode est très efficace. Elle s’applique plus généralement aux séries trigonométriques et fournit aussi un procédé de sommation des séries alternées divergentes; par exemple, pour la série de Leibniz 1 漣 1 + 1 漣 ..., elle donne aussitôt le résultat 1/2. Les recherches d’Euler dans ce domaine ont été systématisées par Lacroix et Poncelet.

Encyclopédie Universelle. 2012.